//
// Created by Administrator on 2021/5/15.
//

/*
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。*/

#include <vector>
#include <iostream>
#include <stack>

using namespace std;

class Solution {
public:
    // 暴力  超时
    int largestRectangleArea1(vector<int> &heights) { // 枚举宽度
        int ans = 0;
        for (int i = 0; i < heights.size(); ++i) { // 遍历柱子
            int minHeight = heights[i];
            // 从这个柱子往后遍历，找到最低的高度
            for (int j = i + 1; j < heights.size(); ++j) {
                minHeight = min(minHeight, heights[j]);
                ans = max(ans, (j - i + 1) * minHeight);
            }
        }
        return ans;
    }

    // 暴力 超时
    int largestRectangleArea2(vector<int> &heights) { // 枚举高度
        int n = (int) heights.size();
        int ans = 0;
        for (int mid = 0; mid < n; ++mid) {
            // 枚举高
            int height = heights[mid];
            int left = mid, right = mid;
            // 确定左右边界
            while (left - 1 >= 0 && heights[left - 1] >= height) {
                --left;
            }
            while (right + 1 < n && heights[right + 1] >= height) {
                ++right;
            }
            // 计算面积
            ans = max(ans, (right - left + 1) * height);
        }
        return ans;
    }

    int largestRectangleArea3(vector<int> &heights) {
        /**对枚举高度法的改进
         * 枚举高度时，需要知道左右两侧最近的小于该高度的矩形
         * 用单调栈，左右各遍历一次，同样可以得到
         */

        int n = static_cast<int>(heights.size());
        vector<int> left(n), right(n); // 储存左右最近的小于当前位置高度的矩形的位置

        stack<int> mono_stack; // 单调栈
        // 从左到右遍历
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                mono_stack.pop();
            }
            left[i] = (mono_stack.empty() ? -1 : mono_stack.top()); // 栈顶是符合要求的矩形  进行记录
            mono_stack.push(i);
        }
        // 从右到左遍历
        mono_stack = stack<int>();
        for (int i = n - 1; i >= 0; --i) {
            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                mono_stack.pop();
            }
            right[i] = (mono_stack.empty() ? n : mono_stack.top());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, (right[i] - left[i] - 1) * heights[i]); // 求最大面积
        }
        return ans;

    }

    int largestRectangleArea4(vector<int> &heights) { // 单调栈 + 常数优化
        int n = (int) heights.size();
        vector<int> left(n, -1), right(n, n);

        stack<int> mono_stack;
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
                /**这里直接记录右边界
                 * 由于判断条件是>= ，如果有多个等高的矩形，那么此时栈顶矩形将无法得到正确的有边界
                 * 但是最右边的矩形得到的是正确的右边界，这对于答案来说没有影响。
                 */
                right[mono_stack.top()] = i;
                mono_stack.pop();
            }
            left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
            mono_stack.push(i);
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }

    int largestRectangleArea5(vector<int> &heights) { // 单调栈 + 常数优化
        int n = heights.size();
        vector<int> left(n, -1), right(n, n);
        stack<int> mono;
        for (int i = 0; i < n; ++i) {
            while (!mono.empty() and heights[i] <= heights[mono.top()]) {
                right[mono.top()] = i;
                mono.pop();
            }
            left[i] = (mono.empty() ? -1 : mono.top());
            mono.push(i);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;

    }

};

int main() {
    Solution sol;
    vector<int> height{2, 1, 5, 6, 2, 3};
    cout << sol.largestRectangleArea5(height) << endl;
    return 0;
}